package main.old.new_2023.last.month_6;

import main.dataStruct.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Description:
 * todo 1254. 统计封闭岛屿的数目
 * 二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，
 * 封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
 * 请返回 封闭岛屿 的数目。
 *
 * todo 剑指 Offer 32 - I. 从上到下打印二叉树
 * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
 *
 * todo 剑指 Offer 32 - II. 从上到下打印二叉树 II
 * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0618 {

    //从上到下打印二叉树 II
    public List<List<Integer>> levelOrderTWO(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null){
            return lists;
        }
        Queue<TreeNode> queList = new LinkedList<>();
        queList.offer(root);
        while (queList.peek() != null){
            List<Integer> ans = new ArrayList<>();
            int size = queList.size();
            for (int i = 0; i< size; i++){
               TreeNode poll = queList.poll();
               ans.add(poll.val);
               if (poll.left != null){
                   queList.add(poll.left);
               }
               if (poll.right != null){
                   queList.add(poll.right);
               }
           }
            lists.add(ans);
        }
        return lists;
    }

    //从上到下打印二叉树
    public int[] levelOrder(TreeNode root) {
        //同一层先左到右，使用队列先进先出的特性，可以将节点从左到右set，然后按顺序放出然后记录节点
        if (root == null){
            return new int[0];
        }
        Queue<TreeNode> queList = new LinkedList<>();
        queList.add(root);
        List<Integer> ans = new ArrayList<>();
        while (queList.peek() != null){
            TreeNode poll = queList.poll();
            ans.add(poll.val);
            if (poll.left != null){
                queList.add(poll.left);
            }
            if (poll.right != null){
                queList.add(poll.right);
            }
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++){
            res[i] = ans.get(i);
        }
        return res;
    }

    //统计封闭岛屿的数目
    public int closedIsland(int[][] grid) {
        //首先，边界的0不算岛屿，可以先把边界以及相连的改为1，用递归的算法，上下左右延展，将一整块岛变成1，对二维数字，进行轮训计算
        int m = grid.length, n=grid[0].length;
        for (int i =0;i < m;i++){
            //一次加多少
            int step = (i == m-1 || i == 0) ? 1 : n-1;
            for (int j = 0; j < n; j += step){
                dfs(grid, i, j);
            }
        }
        int result = 0;
        for (int i =1;i<m-1;i++){
            for (int j = 1;j < n-1;j++){
                if (grid[i][j] ==0){
                    result++;
                    dfs(grid, i, j);
                }
            }
        }
        return result;
    }

    //批量将 0 变成 1
    private void dfs(int[][] grid,int x ,int y){
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[x].length || grid[x][y] != 0){
            return;
        }
        grid[x][y] = 1;
        dfs(grid,x-1,y);
        dfs(grid,x+1,y);
        dfs(grid,x,y-1);
        dfs(grid,x,y+1);
    }
}
